package datastruct.linkedlist;

import java.util.Objects;
import java.util.function.Consumer;

/**
 * 单链表
 */
public class SingleLinkedList<T> {

    // 长度
    private int size;
    // 头节点(不参与遍历)
    private Node<T> head = new Node<>(null);

    private static class Node<T> {
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    /**
     * 根据索引找到节点的前一个节点
     */
    private Node<T> node(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("索引越界");
        }
        Node<T> temp = head;
        for (int i = 0; i < size; i++) {
            temp = temp.next;
        }
        return temp;
    }

    public void forEach(Consumer<T> consumer) {
        Node<T> temp = head.next;
        for (int i = 0; i < size; i++) {
            consumer.accept(temp.data);
            temp = temp.next;
        }
    }

    public void add(T data) {
        add(size, data);
    }

    public void add(int index, T data) {
        Node<T> before;
        if (index == size) {
            before = head;
            for (int i = 0; i < size; i++) {
                before = before.next;
            }
        } else {
            before = node(index);

        }
        Node<T> node = new Node<>(data);
        node.next = before.next;
        before.next = node;
        size++;
    }

    public void delete(int index) {
        Node<T> before = node(index);
        before.next = before.next.next;

        before.data = null;
        before.next = null;

        size--;
    }

    public void update(int index, T data) {
        node(index).next.data = data;
    }

    public T get(int index) {
        return node(index).next.data;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        forEach(data -> builder.append(data).append(", "));
        int len = builder.length();
        if (len > 2) {
            builder.delete(len - 2, len);
        }
        return builder.insert(0, "[").append("]").toString();
    }

    /**
     * 找到倒数第k个元素(采用快慢指针法，且不使用size字段)
     */
    public T findLast(int k) {
        // 快指针
        Node<T> fast = head;
        // 慢指针
        Node<T> slow = head;

        // fast第一次走的步数
        int count = 0;
        // fast先走 k-1 步
        for (; (count < k - 1) && (fast.next != null); count++) {
            fast = fast.next;
        }

        // 判断是否越界
        if (count != k - 1) {
            throw new IndexOutOfBoundsException("索引越界");
        }

        // fast走到最后一个，slow就停在倒数第k个
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.data;
    }

    /**
     * 逆转链表
     */
    public void reserve() {
        // 前一个节点
        Node<T> prev = null;
        // 当前节点
        Node<T> cur = head.next;

        while (cur != null) {
            // 后一个节点
            Node<T> temp = cur.next;
            // 逆转
            cur.next = prev;
            prev = cur;
            // head的下一个每次连到当前节点
            head.next = cur;
            cur = temp;
        }

        // 逆转链表 递归做法
        // if (head.next != null) {
        //     reserve(head);
        // }
    }

    /**
     * 逆转链表 递归做法
     */
    public void reserve(Node<T> node) {
        Node<T> next = node.next;
        if (next != null) {
            head.next = next;
            reserve(next);
            next.next = (node != head) ? node : null;
        }
    }

    /**
     * 倒序遍历
     */
    public void forEachReverse(Consumer<T> consumer) {
        Objects.requireNonNull(consumer);
        forEachReverse(head, consumer);
    }

    private void forEachReverse(Node<T> node, Consumer<T> consumer) {
        Node<T> next = node.next;
        if (next != null) {
            // 递归：先遍历下一个
            forEachReverse(next, consumer);
            consumer.accept(next.data);
        }
    }
}
